#include <iostream>

using namespace std;

/*
template <typename T>
void QuickSort(T arr[], int start, int end){
	if(start == end)
		return;
	T key = arr[start];
	
	int first = start, last = end;
	while(key < arr[last] && first != last)
		last --;
	if(key >= arr[last] && first != last){
		arr[first++] = arr[last];
		arr[last] = key;
	}
	while(key > arr[first] && first != last)
		first ++;
	if(key <= arr[first] && first != last){
		arr[last] = arr[first];
		arr[first] = key;
	}
	if(first == start || last == end)
		return;
	QuickSort(arr, start, first);
	QuickSort(arr, first, end);
}
*/

template <typename T>
void QuickSort(T arr[], int begin, int end){
	if(begin >= end)
		return;	
	int pivot = begin, first = begin, last = end;
	T temp;
	while(first <= last){
		while(arr[last] > arr[pivot] && first <= last)
			last --;
		if(arr[last] <= arr[pivot] && first <= last){
			temp = arr[last];
			arr[last] = arr[pivot];
			arr[pivot] = temp;
			pivot = last;
		}
		while(arr[first] <= arr[pivot] && last >= first)
			first ++;
		if(arr[first] > arr[pivot] && first <= last){
			temp = arr[first];
			arr[first] = arr[pivot];
			arr[pivot] = temp;
			pivot = first;
		}
	}
	QuickSort(arr, begin, pivot - 1);
	QuickSort(arr, pivot + 1, end);
}


void testQuickSort(){
	//int arr[] = {3, 2, 5, 6, 9, 1, 4, 8, 10, 12};
	int arr[] = {2, 1};
	int size = sizeof(arr) / sizeof(int);
	QuickSort<int>(arr, 0, size - 1);

	int index = 0;
	while(index <size)
		cout << arr[index ++] << endl;
	getchar();
}